{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "14907b90",
   "metadata": {},
   "source": [
    "## 第2章 搜索问题\n",
    "\n",
    "### 2.1 DNA搜索"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "3a691c0e",
   "metadata": {},
   "outputs": [],
   "source": [
    "from enum import IntEnum\n",
    "from typing import Tuple, List\n",
    "\n",
    "Nucleotide: IntEnum = IntEnum('Nucleotide', ('A', 'C', 'G', 'T'))\n",
    "Codon = Tuple[Nucleotide, Nucleotide, Nucleotide]  # type alias for codons\n",
    "Gene = List[Codon]  # type alias for genes\n",
    "gene_str: str = \"ACGTGGCTCTCTAACGTACGTACGTACGGGGTTTATATATACCCTAGGACTCCCTTT\"\n",
    "\n",
    "def string_to_gene(s: str) -> Gene:\n",
    "    gene: Gene = []\n",
    "    for i in range(0, len(s), 3):\n",
    "        if (i + 2) >= len(s):  # don't run off end!\n",
    "            return gene\n",
    "        #  initialize codon out of three nucleotides\n",
    "        codon: Codon = (Nucleotide[s[i]], Nucleotide[s[i + 1]], Nucleotide[s[i + 2]])\n",
    "        gene.append(codon)  # add codon to gene\n",
    "    return gene"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "7dbe3e4c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "my_gene: Gene = string_to_gene(gene_str)\n",
    "\n",
    "def linear_contains(gene: Gene, key_codon: Codon) -> bool:\n",
    "    for codon in gene:\n",
    "        if codon == key_codon:\n",
    "            return True\n",
    "    return False\n",
    "\n",
    "acg: Codon = (Nucleotide.A, Nucleotide.C, Nucleotide.G)\n",
    "gat: Codon = (Nucleotide.G, Nucleotide.A, Nucleotide.T)\n",
    "print(linear_contains(my_gene, acg))  # True\n",
    "print(linear_contains(my_gene, gat))  # False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "4efed331",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "def binary_contains(gene: Gene, key_codon: Codon) -> bool:\n",
    "    low: int = 0\n",
    "    high: int = len(gene) - 1\n",
    "    while low <= high:  # while there is still a search space\n",
    "        mid: int = (low + high) // 2\n",
    "        if gene[mid] < key_codon:\n",
    "            low = mid + 1\n",
    "        elif gene[mid] > key_codon:\n",
    "            high = mid - 1\n",
    "        else:\n",
    "            return True\n",
    "    return False\n",
    "\n",
    "my_sorted_gene: Gene = sorted(my_gene)\n",
    "print(binary_contains(my_sorted_gene, acg))  # True\n",
    "print(binary_contains(my_sorted_gene, gat))  # False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "f65ff91d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "from __future__ import annotations\n",
    "from typing import TypeVar, Iterable, Sequence, Generic, List, Callable, Set, Deque, Dict, Any, Optional, Protocol\n",
    "#from typing_extensions import Protocol\n",
    "from heapq import heappush, heappop\n",
    "\n",
    "T = TypeVar('T')\n",
    "\n",
    "def linear_contains(iterable: Iterable[T], key: T) -> bool:\n",
    "    for item in iterable:\n",
    "        if item == key:\n",
    "            return True\n",
    "    return False\n",
    "\n",
    "C = TypeVar(\"C\", bound=\"Comparable\")\n",
    "\n",
    "class Comparable(Protocol):\n",
    "    def __eq__(self, other: Any) -> bool:\n",
    "       ...\n",
    "    def __lt__(self: C, other: C) -> bool:\n",
    "       ...\n",
    "    def __gt__(self: C, other: C) -> bool:\n",
    "        return (not self < other) and self != other\n",
    "\n",
    "    def __le__(self: C, other: C) -> bool:\n",
    "        return self < other or self == other\n",
    "\n",
    "    def __ge__(self: C, other: C) -> bool:\n",
    "        return not self < other\n",
    "\n",
    "def binary_contains(sequence: Sequence[C], key: C) -> bool:\n",
    "    low: int = 0\n",
    "    high: int = len(sequence) - 1\n",
    "    while low <= high:  # while there is still a search space\n",
    "        mid: int = (low + high) // 2\n",
    "        if sequence[mid] < key:\n",
    "            low = mid + 1\n",
    "        elif sequence[mid] > key:\n",
    "            high = mid - 1\n",
    "        else:\n",
    "            return True\n",
    "    return False\n",
    "\n",
    "\n",
    "print(linear_contains([1, 5, 15, 15, 15, 15, 20], 5))  # True\n",
    "print(binary_contains([\"a\", \"d\", \"e\", \"f\", \"z\"], \"f\"))  # True\n",
    "print(binary_contains([\"john\", \"mark\", \"ronald\", \"sarah\"], \"sheila\"))  # False"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4a594405",
   "metadata": {},
   "source": [
    "### 2.2 求解迷宫问题\n",
    "\n",
    "下面代码引用了[generic_search模块](https://github.com/WillKoehrsen/classic_computer_science)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "d9d90c2e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Maze.py\n",
    "from enum import Enum\n",
    "from typing import List, NamedTuple, Callable, Optional\n",
    "import random\n",
    "from math import sqrt\n",
    "\n",
    "class Cell(str, Enum):\n",
    "    EMPTY = \" \"\n",
    "    BLOCKED = \"X\"\n",
    "    START = \"S\"\n",
    "    GOAL = \"G\"\n",
    "    PATH = \"*\"\n",
    "\n",
    "class MazeLocation(NamedTuple):\n",
    "    row: int\n",
    "    column: int\n",
    "\n",
    "class Maze:\n",
    "    def __init__(self, rows: int = 10, columns: int = 10, sparseness: float = 0.2, start: \\\n",
    "        MazeLocation = MazeLocation(0, 0), goal: MazeLocation = MazeLocation(9, 9)) -> None:\n",
    "        # initialize basic instance variables\n",
    "        self._rows: int = rows\n",
    "        self._columns: int = columns\n",
    "        self.start: MazeLocation = start\n",
    "        self.goal: MazeLocation = goal\n",
    "        # fill the grid with empty cells\n",
    "        self._grid: List[List[Cell]] = [[Cell.EMPTY for c in range(columns)] \n",
    "    for r in range(rows)]\n",
    "        # populate the grid with blocked cells\n",
    "        self._randomly_fill(rows, columns, sparseness)\n",
    "        # fill the start and goal locations in\n",
    "        self._grid[start.row][start.column] = Cell.START\n",
    "        self._grid[goal.row][goal.column] = Cell.GOAL\n",
    "\n",
    "    def _randomly_fill(self, rows: int, columns: int, sparseness: float):\n",
    "        for row in range(rows):\n",
    "            for column in range(columns):\n",
    "                if random.uniform(0, 1.0) < sparseness:\n",
    "                    self._grid[row][column] = Cell.BLOCKED\n",
    "    # return a nicely formatted version of the maze for printing\n",
    "    def __str__(self) -> str:\n",
    "        output: str = \"\"\n",
    "        for row in self._grid:\n",
    "            output += \"\".join([c.value for c in row]) + \"\\n\"\n",
    "        return output\n",
    "    def goal_test(self, ml: MazeLocation) -> bool:\n",
    "        return ml == self.goal\n",
    "    def successors(self, ml: MazeLocation) -> List[MazeLocation]:\n",
    "        locations: List[MazeLocation] = []\n",
    "        if ml.row + 1 < self._rows and self._grid[ml.row + 1][ml.column] != Cell.BLOCKED:\n",
    "            locations.append(MazeLocation(ml.row + 1, ml.column))\n",
    "        if ml.row - 1 >= 0 and self._grid[ml.row - 1][ml.column] != Cell.BLOCKED:\n",
    "            locations.append(MazeLocation(ml.row - 1, ml.column))\n",
    "        if ml.column + 1 < self._columns and self._grid[ml.row][ml.column + 1] != Cell.BLOCKED:\n",
    "            locations.append(MazeLocation(ml.row, ml.column + 1))\n",
    "        if ml.column - 1 >= 0 and self._grid[ml.row][ml.column - 1] != Cell.BLOCKED:\n",
    "            locations.append(MazeLocation(ml.row, ml.column - 1))\n",
    "        return locations\n",
    "    \n",
    "    def mark(self, path: List[MazeLocation]):\n",
    "        for maze_location in path:\n",
    "            self._grid[maze_location.row][maze_location.column] = Cell.PATH\n",
    "        self._grid[self.start.row][self.start.column] = Cell.START\n",
    "        self._grid[self.goal.row][self.goal.column] = Cell.GOAL\n",
    "\n",
    "    def clear(self, path: List[MazeLocation]):\n",
    "        for maze_location in path:\n",
    "            self._grid[maze_location.row][maze_location.column] = Cell.EMPTY\n",
    "        self._grid[self.start.row][self.start.column] = Cell.START\n",
    "        self._grid[self.goal.row][self.goal.column] = Cell.GOAL\n",
    "        \n",
    "def euclidean_distance(goal: MazeLocation) -> Callable[[MazeLocation], float]:\n",
    "    def distance(ml: MazeLocation) -> float:\n",
    "        xdist: int = ml.column - goal.column\n",
    "        ydist: int = ml.row - goal.row\n",
    "        return sqrt((xdist * xdist) + (ydist * ydist))\n",
    "    return distance\n",
    "\n",
    "def manhattan_distance(goal: MazeLocation) -> Callable[[MazeLocation], float]:\n",
    "    def distance(ml: MazeLocation) -> float:\n",
    "        xdist: int = abs(ml.column - goal.column)\n",
    "        ydist: int = abs(ml.row - goal.row)\n",
    "        return (xdist + ydist)\n",
    "    return distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "93a77406",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "S X    XX \n",
      "  X   X X \n",
      "          \n",
      "     X   X\n",
      "     XX   \n",
      "X      X G\n",
      "\n",
      "路径解算中...\n",
      "路径解算历时: 0.000534s\n",
      "S*X    XX \n",
      " *X   X X \n",
      "**  ***** \n",
      "*   *X  *X\n",
      "*****XX **\n",
      "X      X G\n",
      "\n"
     ]
    }
   ],
   "source": [
    "from generic_search import dfs, node_to_path, Node\n",
    "from time import perf_counter as tic\n",
    "\n",
    "# Test DFS\n",
    "m: Maze = Maze(6, 10, 0.2, MazeLocation(0, 0), MazeLocation(5, 9))\n",
    "print(m)\n",
    "print(\"路径解算中...\")\n",
    "st = tic()\n",
    "solution1: Optional[Node[MazeLocation]] = dfs(m.start, m.goal_test, m.successors)\n",
    "print(\"路径解算历时: {:5f}s\".format(tic() - st))\n",
    "if solution1 is None:\n",
    "    print(\"No solution found using depth-first search!\")\n",
    "else:\n",
    "    path1: List[MazeLocation] = node_to_path(solution1)\n",
    "    m.mark(path1)\n",
    "    print(m)\n",
    "    m.clear(path1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "bb2b4762",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "路径解算中...\n",
      "路径解算历时: 0.001139s\n",
      "S X    XX \n",
      "* X   X X \n",
      "*******   \n",
      "     X** X\n",
      "     XX** \n",
      "X      X*G\n",
      "\n"
     ]
    }
   ],
   "source": [
    "from generic_search import bfs\n",
    "from time import perf_counter as tic\n",
    "\n",
    "# Test BFS\n",
    "print(\"路径解算中...\")\n",
    "st = tic()\n",
    "solution2: Optional[Node[MazeLocation]] = bfs(m.start, m.goal_test, m.successors)\n",
    "print(\"路径解算历时: {:5f}s\".format(tic() - st))\n",
    "if solution2 is None:\n",
    "    print(\"No solution found using breadth-first search!\")\n",
    "else:\n",
    "    path2: List[MazeLocation] = node_to_path(solution2)\n",
    "    m.mark(path2)\n",
    "    print(m)\n",
    "    m.clear(path2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "1f5419e3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "路径解算中...\n",
      "路径解算历时: 0.001013s\n",
      "S X    XX \n",
      "* X   X X \n",
      "*******   \n",
      "     X** X\n",
      "     XX** \n",
      "X      X*G\n",
      "\n"
     ]
    }
   ],
   "source": [
    "from generic_search import astar\n",
    "from time import perf_counter as tic\n",
    "# Test A*\n",
    "distance: Callable[[MazeLocation], float] = manhattan_distance(m.goal)\n",
    "print(\"路径解算中...\")\n",
    "st = tic()\n",
    "solution3: Optional[Node[MazeLocation]] = astar(m.start, m.goal_test, m.successors, distance)\n",
    "print(\"路径解算历时: {:5f}s\".format(tic() - st))\n",
    "if solution3 is None:\n",
    "    print(\"No solution found using A*!\")\n",
    "else:\n",
    "    path3: List[MazeLocation] = node_to_path(solution3)\n",
    "    m.mark(path3)\n",
    "    print(m)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a8ef8fab",
   "metadata": {},
   "source": [
    "### 2.3 传教士和食人族"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "695d24fe",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "西岸 有3个传教士和3个食人族.\n",
      "东岸 有0个传教士和0个食人族.\n",
      "小船在 西岸.\n",
      "0 个传教士和 2 个食人族 西岸 >>>...东岸.\n",
      "\n",
      "西岸 有3个传教士和1个食人族.\n",
      "东岸 有0个传教士和2个食人族.\n",
      "小船在 东岸.\n",
      "0 个传教士和 1 个食人族 东岸 >>>...西岸.\n",
      "\n",
      "西岸 有3个传教士和2个食人族.\n",
      "东岸 有0个传教士和1个食人族.\n",
      "小船在 西岸.\n",
      "0 个传教士和 2 个食人族 西岸 >>>...东岸.\n",
      "\n",
      "西岸 有3个传教士和0个食人族.\n",
      "东岸 有0个传教士和3个食人族.\n",
      "小船在 东岸.\n",
      "0 个传教士和 1 个食人族 东岸 >>>...西岸.\n",
      "\n",
      "西岸 有3个传教士和1个食人族.\n",
      "东岸 有0个传教士和2个食人族.\n",
      "小船在 西岸.\n",
      "2 个传教士和 0 个食人族 西岸 >>>...东岸.\n",
      "\n",
      "西岸 有1个传教士和1个食人族.\n",
      "东岸 有2个传教士和2个食人族.\n",
      "小船在 东岸.\n",
      "1 个传教士和 1 个食人族 东岸 >>>...西岸.\n",
      "\n",
      "西岸 有2个传教士和2个食人族.\n",
      "东岸 有1个传教士和1个食人族.\n",
      "小船在 西岸.\n",
      "2 个传教士和 0 个食人族 西岸 >>>...东岸.\n",
      "\n",
      "西岸 有0个传教士和2个食人族.\n",
      "东岸 有3个传教士和1个食人族.\n",
      "小船在 东岸.\n",
      "0 个传教士和 1 个食人族 东岸 >>>...西岸.\n",
      "\n",
      "西岸 有0个传教士和3个食人族.\n",
      "东岸 有3个传教士和0个食人族.\n",
      "小船在 西岸.\n",
      "0 个传教士和 2 个食人族 西岸 >>>...东岸.\n",
      "\n",
      "西岸 有0个传教士和1个食人族.\n",
      "东岸 有3个传教士和2个食人族.\n",
      "小船在 东岸.\n",
      "1 个传教士和 0 个食人族 东岸 >>>...西岸.\n",
      "\n",
      "西岸 有1个传教士和1个食人族.\n",
      "东岸 有2个传教士和2个食人族.\n",
      "小船在 西岸.\n",
      "1 个传教士和 1 个食人族 西岸 >>>...东岸.\n",
      "\n",
      "西岸 有0个传教士和0个食人族.\n",
      "东岸 有3个传教士和3个食人族.\n",
      "小船在 东岸.\n"
     ]
    }
   ],
   "source": [
    "from __future__ import annotations\n",
    "from typing import List, Optional\n",
    "from generic_search import bfs, Node, node_to_path\n",
    "\n",
    "MAX_NUM: int = 3\n",
    "\n",
    "class MCState:\n",
    "    def __init__(self, missionaries: int, cannibals: int, boat: bool) -> None:\n",
    "        self.wm: int = missionaries # west bank missionaries\n",
    "        self.wc: int = cannibals # west bank cannibals\n",
    "        self.em: int = MAX_NUM - self.wm  # east bank missionaries\n",
    "        self.ec: int = MAX_NUM - self.wc  # east bank cannibals\n",
    "        self.boat: bool = boat\n",
    "\n",
    "    def __str__(self) -> str:\n",
    "        return (f\"西岸 有{self.wm}个传教士和{self.wc}个食人族.\\n\" \n",
    "                f\"东岸 有{self.em}个传教士和{self.ec}个食人族.\\n\"\n",
    "                f\"小船在 {'西' if self.boat else '东'}岸.\")\n",
    "    \n",
    "    def goal_test(self) -> bool:\n",
    "        return self.is_legal and self.em == MAX_NUM and self.ec == MAX_NUM\n",
    "    @property\n",
    "    def is_legal(self) -> bool:\n",
    "        if self.wm < self.wc and self.wm > 0:\n",
    "            return False\n",
    "        if self.em < self.ec and self.em > 0:\n",
    "            return False\n",
    "        return True\n",
    "    def successors(self) -> List[MCState]:\n",
    "        sucs: List[MCState] = []\n",
    "        if self.boat: # boat on west bank\n",
    "            if self.wm > 1:\n",
    "                sucs.append(MCState(self.wm - 2, self.wc, not self.boat))\n",
    "            if self.wm > 0:\n",
    "                sucs.append(MCState(self.wm - 1, self.wc, not self.boat))\n",
    "            if self.wc > 1:\n",
    "                sucs.append(MCState(self.wm, self.wc - 2, not self.boat))\n",
    "            if self.wc > 0:\n",
    "                sucs.append(MCState(self.wm, self.wc - 1, not self.boat))\n",
    "            if (self.wc > 0) and (self.wm > 0):\n",
    "                sucs.append(MCState(self.wm - 1, self.wc - 1, not self.boat))\n",
    "        else: # boat on east bank\n",
    "            if self.em > 1:\n",
    "                sucs.append(MCState(self.wm + 2, self.wc, not self.boat))\n",
    "            if self.em > 0:\n",
    "                sucs.append(MCState(self.wm + 1, self.wc, not self.boat))\n",
    "            if self.ec > 1:\n",
    "                sucs.append(MCState(self.wm, self.wc + 2, not self.boat))\n",
    "            if self.ec > 0:\n",
    "                sucs.append(MCState(self.wm, self.wc + 1, not self.boat))\n",
    "            if (self.ec > 0) and (self.em > 0):\n",
    "                sucs.append(MCState(self.wm + 1, self.wc + 1, not self.boat))\n",
    "        return [x for x in sucs if x.is_legal]\n",
    "    \n",
    "def display_solution(path: List[MCState]):\n",
    "    if len(path) == 0: # sanity check\n",
    "        return\n",
    "    old_state: MCState = path[0]\n",
    "    print(old_state)\n",
    "    for current_state in path[1:]:\n",
    "        if current_state.boat:\n",
    "            print(f\"{old_state.em - current_state.em} 个传教士和 \" +\n",
    "                  f\"{old_state.ec - current_state.ec} 个食人族\" +\n",
    "                  \" 东岸 >>>...西岸.\\n\")\n",
    "        else:\n",
    "            print(f\"{old_state.wm - current_state.wm} 个传教士和 \" +\n",
    "                  f\"{old_state.wc -current_state.wc} 个食人族\" +\n",
    "                  \" 西岸 >>>...东岸.\\n\")\n",
    "        print(current_state)\n",
    "        old_state = current_state\n",
    "        \n",
    "start: MCState = MCState(MAX_NUM, MAX_NUM, True)\n",
    "solution: Optional[Node[MCState]] = bfs(start, MCState.goal_test, MCState.successors)\n",
    "if solution is None:\n",
    "    print(\"无解!\")\n",
    "else:\n",
    "    path: List[MCState] = node_to_path(solution)\n",
    "    display_solution(path)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "09ea07a1",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "celltoolbar": "Raw Cell Format",
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
